今天的題目原出處是 №1029 (https://leetcode.com/problems/two-city-scheduling/),算是較新的題目。簡單來說就是有 2N
個人要把他們丟到 A 跟 B 兩個城市,每個人要被丟到 A 或 B 都有各自的 Cost,最後關鍵的是兩個城市最後都要有 N
個人囉!
一開始可能會想說,那我就先 “貪婪地” (greedy) 把丟到 A 的 Cost 先排序,把前 N
低的,丟到 A,剩下的人再丟到 B,但很明顯這是有問題的,假設以 Example 1 來說,我們先用丟到 A 的 Cost 進行排序得到 [10, 20], [30, 20], [30, 200], [400, 50]
,結果反而讓丟到 B 的 Cost 大爆炸 (200+50
)。反過來根據 B 的 Cost 排序當然也有問題 (你怎麼知道要用 A 還是 B 的 Cost 來排序?!)
所以這題基本上還是可以用 Greedy 的方式,但是要排序 (升序) 的是 “丟到 Cost A 和 Cost B 的差”!我們先以這個思想把 Example 1 排出來會得到 [30, 200], [10, 20], [30, 20], [400, 50]
(因為 “差” 的排序是 -170, -10, 10, 350
),因為這裡只有四個人,所以我們就把前兩個就會丟到 A (30
and 10
),後兩個則是丟到 B (20
and 50
)。這樣排序的理由是,以 [30, 200]
來說,要是我不選 A (30
),而選了 B (200
),那麼成本會比選 A 大大地多了 170
,為了不讓這個情況發生,我這時候更一定要選 A 了,這樣你有感覺了嗎?讓我們再看最後一個 [400, 50]
,要是此時我不選 B,而是選 A,那麼選 A 的成本就會比選 B 的成本大大增加了 350
!相信聰明的人看到這應該已經懂了!那麼最後就讓我們來看 Code 。
Code 的部分就跟上述一模一樣啦!Line 3 作排序,而排序是根據 “丟到 Cost A 和 Cost B 的差” (x[0]-x[1]
) ,再來就是把前 N 個的 Cost of A 放到 totalCost
,以及把後 N 個的 Cost of B 放到 totalCost
。就醬!
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
sortedCosts = sorted(costs, key=lambda x: x[0] - x[1])
totalCost = 0
for i in range(len(costs)//2):
totalCost += sortedCosts[i][0]
for i in range(len(costs)//2, len(costs)):
totalCost += sortedCosts[i][1]
return totalCost
彩蛋!如果你想要用 DP 的話該怎麼做呢?記得 DP 兩部曲嗎?狀態的定義,以及狀態轉移方程式 (忘記的看 這裡 )。這裡原先的問題是,如果有 2N
個人,其中某 N
個人在 A (代表其他 2N-N=N
的人在 B) 的 Cost,那麼子問題就是如果有 i
個人,其中 j
個人在 A (代表其他 i-j
的人在 B) 的 Cost 是多少。因此 dp[i][j]
就是如果有 i
個人,其中 j
個人在 A 的 Cost 啦!狀態轉移方程式則是 dp[i][j] = min(dp[i-1][j] + costs[i-1][1], dp[i-1][j-1] + costs[i-1][0])
,就是看 1. 把 i
是丟到 A 2. 把i
丟到 B 哪一個成本比較小。(這裡要注意的是 costs[i-1]
的 i-1
是因為這裡 i
是指第 i
個人,但是 costs 是從 0 開始。) 不過 DP 要花的時間跟空間自然比較高囉!(O(N²))
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
dp = [[float('inf') for j in range(len(costs)//2 + 1)] for i in range(len(costs) + 1)]
dp[0][0] = 0
for i in range(1, (len(costs) // 2) + 1):
dp[i][0] = dp[i-1][0] + costs[i-1][1]
for i in range(1, len(costs) + 1):
for j in range(1, len(costs) // 2 + 1):
dp[i][j] = min(dp[i-1][j] + costs[i-1][1], dp[i-1][j-1] + costs[i-1][0])
return dp[len(costs)][len(costs) // 2]
See YA!
歡迎追蹤我的 Medium 囉!
https://medium.com/@ryanyang1221